package ans.p1011;

import test.Entrance;

import java.util.Arrays;

/**
 * #      1011
 * 名称   在 D 天内送达包裹的能力
 * 链接   https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days
 * 题解   [184](https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution)
 * 通过率 56.6%
 * 难道   中等
 */

public class Solution {

    public int shipWithinDays1(int[] weights, int D) {
        // 确定二分查找左右边界
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = (left + right) / 2;
            // need 为需要运送的天数
            // cur 为当前这一天已经运送的包裹重量之和
            int need = 1, cur = 0;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= D) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }


    @Entrance
    public int shipWithinDays(int[] weights, int D) {
        int l = 0, h = 0;
        for (int weight : weights) {
            l = Math.max(l, weight);
            h += weight;
        }
        while (l < h) {
            int mid = (l + h) / 2;
            if (check(weights, mid, D)) {
                h = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(int[] weights, int w, int D) {
        int t = 0, d = 1;
        for (int weight : weights) {
            if (t + weight > w) {
                d++;
                t = 0;
            }
            t += weight;

        }
        return d <= D;
    }
}